package com.mzy.linear_struct.hot100.链表;

import javax.lang.model.element.VariableElement;

/**
 * @Author: mizy3
 * @Date: 2024/08/07/下午1:41
 * @Description:
 */
public class Pro148排序链表 {



    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // s
        // 4 2 1 3
        // f
        ListNode mid = head;
        ListNode helper = head;
        helper = helper.next;

        while (helper != null && helper.next != null) {
            mid = mid.next;
            helper = helper.next.next;
        }
        // 从中点断开

        ListNode right = mid.next;
        mid.next = null;
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        ListNode l = sortList(head);
        ListNode r = sortList(right);

        while (l != null && r != null) {
            if (l.val < r.val) {
                cur.next = l;
                l = l.next;
            } else {
                cur.next = r;
                r = r.next;
            }
            System.out.println(cur.next.val);
            cur = cur.next;

        }

        while (l != null) {
            cur.next = l;
            l = l.next;
            cur = cur.next;
        }
        while (r != null) {
            cur.next = r;
            r = r.next;
            cur = cur.next;
        }

        return dummy.next;

    }

    public static void main(String[] args) {
        ListNode node = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3, new ListNode(6)))));
        UtilsListNode.print(sortList(node));
    }
}



















